A rate color marker can meter packets in a traffic stream and mark the packets based on traffic parameters. Such metering and marking can be used to enable services such as quality of service or congestion control in communication networks. Two similar color rate markers are documented in Internet Engineering Task Force (IETF) Informational Request For Comments (RFC) 2697 and 2698. See Heinanen, J. and R. Guerin, “A Single Rate Three Color Marker”, RFC 2697, September, 1999, and Heinanen, J. and R. Guerin, “A Two Rate Three Color Marker”, RFC 2698, September, 1999.
The referenced RFCs describe color rate marker algorithms in the context of an Internet Protocol (IP)-based packet switched internetwork. However, such algorithms can be implemented in cell-switched networks as well. Each color marker meters a traffic stream, for example, an IP packet stream, and marks its packets one of green, yellow or red.
The Single Rate Three Color Marker (srTCM) described in RFC2697 marks packets in an IP stream based on a traffic rate, Committed Information Rate (CIR), and two different burst sizes, Committed Burst Size (CBS), and Excess Burst Size (EBS). In short, a packet is marked green if it does not exceed CBS, yellow if it does exceed CBS but does not exceed EBS, and red if it exceeds both CBS and EBS. srTCM is limited in that it uses the length, but not peak rate, of a burst of traffic to determine the color associated with the traffic. A service, or a level of service, is then provided to the traffic based on its color.
The Two Rate Three Color Marker (trTCM) described in RFC 2698 marks packets in an IP stream based on two different traffic rates, Peak Information Rate (PIR), and Committed Information Rate (CIR), and corresponding burst sizes Committed Burst Size (CBS) and Peak Information Burst (PBS). According to trTCM, a packet is marked red if it exceeds PIR, and if the packet does not exceed PIR, it is marked yellow or green depending on whether it exceeds CIR or does not exceed CIR. By making use of two rates, a peak traffic rate (or simply, peak rate), and a committed rate, trTCM is able to monitor peak rate traffic separate from committed rate traffic.
Both srTCM and trTCM contemplate a metering device that meters each packet in a traffic stream and forwards, or passes, the packet to a marker that colors the packet. Both algorithms operate in one of two modes, color-blind mode, in which the meter receives the traffic stream as if it is uncolored, and color-aware mode, in which packets in the received traffic stream are already colored (“pre-colored”), for example, one of colors green, yellow, and red. The details of the pre-coloring process and how the meter detects or determines the color of a packet is implementation specific and outside the scope of the RFCs as well as this invention.
The RFCs disclose the marker recoloring a packet based on the results of the meter, and provide, as an example, coding the color as a codepoint in the Diffserv (DS) field of the packet in a per-hop behavior (PHB) specific manner, and refers one to IETF RFC2474 for further information. See Nichols, K., Blake, S., Baker, F. and D. Black, “Definition of the Differentiated Services Field (DS Field) in the IPv4 and IPv6 Headers”, RFC 2474, December, 1998. The color can be coded as a drop precedence of the packet, according to RFC2597. See Blake, S., Black, D., Carlson, M., Davies, E., Wang, Z. and W. Weiss, “An Architecture for Differentiated Services”, RFC 2475, December 1998.
Both color markers can mark packets in a traffic stream, for example, such that different levels of assurance are provided to packets based on whether the packets are green, yellow or red. Decreasing levels of service may be provided to green, then yellow, then red, packets. For example, green packets may be guaranteed delivery, or at least forwarded with a low probability of being discarded or dropped, while yellow packets may be forwarded on a best effort basis, and red packets dropped.
The RFCs describe Three Color Markers as a way of controlling the admission rate, burst size, and drop precedence of a single stream of packetized data. They do not address how to control these characteristics when the data is divided into multiple streams of different priorities.
Prior approaches to using these markers for data streams with multiple priority levels include:                a. Divide the data into separate streams for each priority using a single marker per priority, or        b. Treat all data of all different priorities as a single data stream using a single marker, or        c. Combine the above two approaches in an hierarchical fashion by first dividing the streams and using a marker per priority, then combining the streams again and meter them with a single, second-level marker.        
The advantages and disadvantages of each approach depend on whether the objective is to control the aggregate rate of the combined stream, or the individual rates of each priority stream. In either case, it is desirable to give preferential treatment to the higher priority traffic. For example, as long as the incoming rate and burst characteristics of the highest priority data stream is within the committed rate and committed burst size of the marker used for that data stream, all of the highest priority data packets should be marked green regardless of how much lower priority data is present. In some cases it is acceptable to control the rate and the burst of each priority stream independently, in which case the first approach above meets the requirements. The disadvantage of this approach is that in the absence of higher priority traffic, the lower priority traffic cannot use the bandwidth reserved for the higher priority traffic. This results in lost bandwidth and inefficient network utilization.
The second approach controls the aggregate rate of all priorities by effectively ignoring the priority. This allows lower priority traffic to consume the full rate in the absence of higher priority traffic, but it cannot provide preferential treatment to higher priority traffic when packets of multiple priorities are intermixed.
The hierarchical structure in the third approach can be configured to partially meet both objectives of giving preferential treatment to higher priority traffic while allowing lower priority traffic to consume full bandwidth in the absence of higher priority traffic. If the sum of the rate and burst sizes of the committed rate buckets for all priorities in the first level is equal to the rate and burst size of the committed rate bucket in the second level, then preferential treatment for higher priority traffic can be guaranteed (within the committed rate and burst size specifications). The sum of the rate and burst sizes of the excess rate buckets for all priorities in the first level can then be configured to exceed the rate and burst size of the excess rate bucket in the second level. This allows any priority traffic to consume the excess bandwidth. The combined effect is that preferential treatment of higher priority traffic is guaranteed within the committed rate and burst size for that priority, but any bandwidth unused by higher priority traffic can only be consumed by lower priority traffic if the lower priority traffic is marked as excess. Significantly, this approach cannot meet both objectives when configured as a single rate two color marker.